package leetcode.editor.cn;

//输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。 
//
// 
//
// 示例 1： 
//
// 输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
//输出：[1,2,3,6,9,8,7,4,5]
// 
//
// 示例 2： 
//
// 输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
//输出：[1,2,3,4,8,12,11,10,9,5,6,7]
// 
//
// 
//
// 限制： 
//
// 
// 0 <= matrix.length <= 100 
// 0 <= matrix[i].length <= 100 
// 
//
// 注意：本题与主站 54 题相同：https://leetcode-cn.com/problems/spiral-matrix/ 
// Related Topics 数组 
// 👍 238 👎 0

public class ShunShiZhenDaYinJuZhenLcof{
    public static void main(String[] args) {
        Solution solution = new ShunShiZhenDaYinJuZhenLcof().new Solution();}

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int[] spiralOrder(int[][] matrix) {
        /*思路：因为此处是对二维数组中的数据进行遍历，直至找到目标数，因此可以考虑使用深度搜索dfs。
        * 对于dfs,需要考虑返回条件、*/

        //考虑二维数组不存在或未初始化的情况
        if(matrix==null || matrix.length==0 ){return new int[0];}

        //获取基本参数
        int rows=matrix.length,  cols=matrix[0].length;
        int total = rows * cols;
        int[] res = new int[total];   //存储结果的数组
        boolean[][] isVisited = new boolean[rows][cols];    //用于标记是否已被访问

        int row=0, col=0;
        int[][] directions = {{0,1},{1,0},{0,-1},{-1,0}};   //用于标记在顺时针时，行与列的变化
        int directionIndex = 0; //记录方向改变次数（右 下 左 上）

        for (int i = 0; i < total; i++) {
            /*思路：按照顺时针的顺序依次遍历二维数组，将对应的数据添加到结果数组中*/
            res[i] = matrix[row][col];  //获取到对应数据
            isVisited[row][col] = true; //标记为已访问
            //该点在顺时针方向上，要继续寻找的下一个点:即行、列均按照上述顺时针的方式进行更新；
            int nextRow = row + directions[directionIndex][0];
            int nextCol = col + directions[directionIndex][1];

            //讨论该点在顺时针四个方向上的行列越界的情况、已被访问的情况,进行调整方向
            if(nextRow<0 || nextRow>=rows || nextCol<0 ||nextCol>=cols || isVisited[nextRow][nextCol]){
                //更新方向：按照改变次数，并4次为一个循环
                directionIndex = (directionIndex + 1)%4;
            }

            //更新行列，方便从下一个节点重新搜寻
            row += directions[directionIndex][0];
            col += directions[directionIndex][1];
        }

        return res;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}